package Domain;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class DFAConstructor {
	HashMap<DfaState,HashMap<Character,DfaState>> _dfaTable;
	DfaDiagram _dfaDiagram;
	
	public DFAConstructor(NFADiagram n)
	{
		_dfaTable = constructDfaTable(n);
		_dfaDiagram = constructDfaDiagram(_dfaTable);
	}
	
	public HashMap<DfaState, HashMap<Character, DfaState>> getDfaTable() {
		return _dfaTable;
	}

	public void setDfaTable(
			HashMap<DfaState, HashMap<Character, DfaState>> _dfaTable) {
		this._dfaTable = _dfaTable;
	}
	
	/**
	 * Construct a DFA from an NFA
	 * @param n The NFA to 
	 */
	private static HashMap<DfaState,HashMap<Character,DfaState>> constructDfaTable(NFADiagram n) {
		// create lookup table for NFA State transitions
		HashMap<NfaState,HashMap<Character,DfaState>> lut = new HashMap();

		// create a table that maps a DfaState to a row, each of which maps a Character to a DfaState
		HashMap<DfaState,HashMap<Character,DfaState>> dfaTable = new HashMap();
		
		// Alphabet
		Set<Character> sigma = new HashSet();
		
		// the open list is the list of states that have not been added to the LUT already
		Queue<NfaState> open = new LinkedList();
		open.add(n.getNfaStart());
		
		// build the lookup table
		NfaState nfaCur;
		LinkedList<NfaState> used = new LinkedList<NfaState>();
		while((nfaCur = open.poll()) != null) {
			DfaState dfaEntry = new DfaState();
		}
		while((nfaCur = open.poll()) != null) {
			HashMap<Character,DfaState> row = new HashMap();
			DfaState dfaEntry = new DfaState();
			
			for (StateTransition t : nfaCur.getTransitions()) {
				// ensure endpoint either has been explored or is added to the queue
				if(!lut.containsKey(t.getEnd())) {
					open.add((NfaState)t.getEnd());
					
				}
				
				// only add entries corresponding to a letter in the alphabet
				if(t.getTransition() == (char)0) continue;
				
				sigma.add(t.getTransition());
				
				AddEpsilonClosure((NfaState)t.getEnd(), dfaEntry);
				
				row.put(t.getTransition(), dfaEntry);		
				
			}
			lut.put(nfaCur, row);
			System.out.println(row.keySet().size());
		}		
		
		// create the initial state of the DFA from the start of the NFA diagram
		// and any states that it has an epsilon-transition to
		DfaState initialState = new DfaState();
		initialState.setId("0");
		AddEpsilonClosure(n.getNfaStart(),initialState);
				
		// start building DFA states
		Queue<DfaState> dfaOpen = new LinkedList();
		dfaOpen.add(initialState);
		DfaState dfaCur;
		// while there's dfa states yet to be explored
		while((dfaCur = dfaOpen.poll()) != null) {
			HashMap<Character,DfaState> row = new HashMap();
			
			// for each character in the alphabet, create an entry, then iterate through
			// all the Nfa States in the Dfa state and look them up in lut
			for(Character c : sigma) {
				DfaState dfaEntry = new DfaState();
				
				for(NfaState ns : dfaCur.getSetOfStates()) {
					DfaState lutEntry = lut.get(ns).get(c);
					if(lutEntry == null) continue;
					
					// if there's a lut entry, union it to the new Dfa Entry
					for(NfaState tempns : lutEntry.getSetOfStates()) {
						dfaEntry.addNfaState(tempns);
						
						// mark the dfa state as terminal if it contains a terminal NFA state
						if(tempns.isTerminal())
							dfaEntry.setTerminal(true);
					}
				}
				
				// go through the state table to see if this state has been
				// added already
				// if it has, associate dfaEntry with the reference in the table
				// to minimize memory use
				// otherwise, add dfaEntry to the open list
				boolean inTable = false;
				for(DfaState stateInTable : dfaTable.keySet()) {
					if(dfaEntry.equals(stateInTable)) {
						dfaEntry = stateInTable;
						inTable = true;
						break;
					}
				}
				if(!inTable){
					dfaOpen.add(dfaEntry);
				}

				row.put(c, dfaEntry);
			}
			
			dfaTable.put(dfaCur, row);
		}
		
		return dfaTable;
	}


	public DfaDiagram constructDfaDiagram(HashMap<DfaState,HashMap<Character,DfaState>> table) {
		DfaDiagram diagram = new DfaDiagram();
		
		// this would be easier after minimization because there's guaranteed to only be one terminal state
		for(DfaState ds : table.keySet()) {
			for(Character c : table.get(ds).keySet()) {
				StateTransition t = new StateTransition();
				t.setStart(ds);
				t.setEnd(table.get(ds).get(c));
				t.setTransition(c);
				ds.addTransition(t);
			}
		}
		return diagram;
	}
	
	/**
	 * Adds the Epsilon Closure of the NFA state to the DFA state
	 * @param s
	 * @param dfaEntry
	 */
	private static void AddEpsilonClosure(NfaState s, DfaState dfaEntry) {
		dfaEntry.addNfaState(s);
		for(StateTransition t : s.getTransitions()) {
			if(t.getTransition() == (char)0 && !dfaEntry.getSetOfStates().contains(t.getEnd())) {
				AddEpsilonClosure((NfaState)t.getEnd(),dfaEntry);
			}
		}
	}



	//for testing
	public static void main(String[] args)
	{
		
	}

}